package leetcode_61_80;

public class minPathSum_64 {
    /**
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径
     * 使得路径上的数字总和为最小。
     * 说明：每次只能向下或者向右移动一步。
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        /**
         * 还是动态规划
         * 从结尾向开头倒推
         * 计算每个格子到达结尾最小路径数字和
         */
        int row=grid.length,col=grid[0].length;
        int [][] dp=new int[row][col]; //存储每个格子到达结尾的最小路径
        //初始化最后一行最后一列
        int count=grid[row-1][col-1];
        dp[row-1][col-1]=count;
        for(int i=row-2;i>=0;i--){           //倒着赋值方便操作
            count+=grid[i][col-1];
            dp[i][col-1]=count;
        }
        count=grid[row-1][col-1];
        for(int i=col-2;i>=0;i--){
            count+=grid[row-1][i];
            dp[row-1][i]=count;
        }
        for(int i=row-2;i>=0;i--){   //行
            for(int t=col-2;t>=0;t--){  //列
                //比较右边和下边的格子对应路径和，哪个更小
                dp[i][t]=grid[i][t]+Math.min(dp[i+1][t],dp[i][t+1]);
            }
        }
        return dp[0][0];
    }

    /**
     * 官解，思路完全一样，但是没有使用额外空间，在原数组上改动
     * 代码也更简洁
     * @param grid
     * @return
     */
    public int minPathSum2(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(i == 0 && j == 0) continue;
                else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

}
